package DataStructure_ZL.栈模拟;

import java.util.Stack;

public class exam {
    /*
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该
压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
 */
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        if (pushA.length == 0 || popA.length == 0) return false;
        MyStack<Integer> iu = new MyStack<>();
        int j = 0;//popA数组
        for (int i = 0; i < pushA.length; i++) {
            if (pushA[i] != popA[j]) {
                iu.push(pushA[i]);
            }

            if (i == pushA.length - 1) {
                while (j < popA.length && !iu.empty()) {
                    if (iu.peek() == popA[j]) {
                        j++;
                        iu.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /*
    有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
     */
    public int evalRPN(String[] tokens) {
        if (tokens.length == 0) return -1;
        Stack<String> iu = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {

            if (tokens[i].equals("+")) {
                iu.push(String.valueOf(Integer.parseInt(iu.pop()) + Integer.parseInt(iu.pop())));
                continue;
            }
            if (tokens[i].equals("-")) {
                int first = Integer.parseInt(iu.pop());
                int second = Integer.parseInt(iu.pop());
                iu.push(String.valueOf(second - first));
                continue;
            }
            if (tokens[i].equals("*")) {
                iu.push(String.valueOf(Integer.parseInt(iu.pop()) * Integer.parseInt(iu.pop())));
                continue;
            }
            if (tokens[i].equals("/")) {
                int first = Integer.parseInt(iu.pop());
                int second = Integer.parseInt(iu.pop());
                iu.push(String.valueOf(second / first));
                continue;
            }
            iu.push(tokens[i]);
        }
        return Integer.parseInt(iu.peek());
    }

    /*
    给定 s 和 t 两个字符串，当它们分别被输入到空白的文本
    编辑器后，如果两者相等，返回 true 。# 代表退格字符。
     */
    public static boolean backspaceCompare(String s, String t) {
        Stack<Character> sIU = new Stack<>();
        Stack<Character> tIU = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '#') {
                if (!sIU.empty()) {
                    sIU.pop();
                }
            } else {
                sIU.push(s.charAt(i));
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == '#') {
                if (!tIU.empty()) {
                    tIU.pop();
                }
            } else {
                tIU.push(t.charAt(i));
            }
        }
        while (!sIU.empty() && !tIU.empty()) {
            if (sIU.pop() != tIU.pop()) {
                return false;
            }
        }
        return sIU.empty() && tIU.isEmpty();
    }
}
